package comeback.sort;

public class MergeSort {
    public static void main(String[] args) {
        int[] num = new int[]{3,2,9,7,1,5,4};
        new MergeSort().mergeSort(num, 0, num.length - 1);
        for (int i = 0; i < num.length; i++) {
            System.out.println(num[i]);
        }
    }

    public void mergeSort(int[] num, int i, int j) {
        if (i >= j) {
            return;
        }
        int mid = (i + j) / 2;
//        mergeSort(num, i, mid - 1);
        // TODO 这种写法可能每次递归的时候mid都比j小，陷入死循环
//        mergeSort(num, mid, j);

        mergeSort(num, i, mid);
        mergeSort(num, mid + 1, j);

        merge(num, i, mid, j);
    }

    private void merge(int[] num, int left, int mid, int right) {
        // TODO 创建两个临时数组，将数组先拷贝到临时数组中，然后对两个有序数组进行排序
        int n1 = mid - left +1;
        int n2 = right - mid;
        int[] num1 = new int[n1];
        int[] num2 = new int[n2];

        for (int i = 0; i < num1.length; i++) {
            num1[i] = num[left + i];
        }
        for (int i = 0; i < num2.length; i++) {
            num2[i] = num[mid + 1 + i];
        }
        // 对两个有序数组排序
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (num1[i] < num2[j]) {
                num[k] = num1[i];
                i++;
            } else {
                num[k] = num2[j];
                j++;
            }
            k++;
        }
        // TODO 将剩余元素合并到原来的数组中
        if (i >= n1) {
            while (j < n2) {
                num[k++] = num2[j++];
            }
        }
        if (j >= n2) {
            while (i < n1) {
                num[k++] = num1[i++];
            }
        }
    }
}
